{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7.4 Analysis of quicksort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.4-1\n",
    "\n",
    "> Show that in the recurrence \n",
    "\n",
    "> $\\displaystyle T(n) = \\max_{0 \\le q \\le n-1}(T(q)+T(n-q-1)) + \\Theta(n)$,\n",
    "\n",
    "> $T(n) = \\Omega(n^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $T(n) \\ge cn^2$,\n",
    "\n",
    "$$\n",
    "\\begin{array}{rlll}\n",
    "T(n) &\\ge& \\displaystyle \\max_{0 \\le q \\le n-1}(cq^2+c(n-q-1)^2) + dn \\\\\n",
    "&\\ge&  c(n-1)^2+dn & \\displaystyle \\left ( q=\\frac{n-1}{2} \\right ) \\\\\n",
    "&=& cn^2 +(d-2c)n+c & \\displaystyle \\left (d>2c\\right ) \\\\\n",
    "&\\ge& cn^2\\\\\n",
    "&=& \\Omega(n^2)\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.4-2\n",
    "\n",
    "> Show that quicksort’s best-case running time is $\\Omega(n \\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$T(n)=2T(n/2)+\\Theta(n)$, therefore it is $\\Omega(n \\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.4-3\n",
    "\n",
    "> Show that the expression $q^2+(n-q-1)^2$ achieves a maximum over $q=0,1, \\dots, n-1$ when $q=0$ or $q=n-1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on the first order derivation on $q$, we know the minimum is achieved when $\\displaystyle q=\\frac{n-1}{2}$, and the function increases with the same speed when $q$ is away from $\\displaystyle \\frac{n-1}{2}$ in two directions. Thus the maximum is on the bound of the the variable, $q=0$ and $q=n-1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.4-4\n",
    "\n",
    "> Show that RANDOMIZED-QUICKSORT’s expected running time is $\\Omega(n \\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\text{E}[X] &=& \\displaystyle \\sum_{i=1}^{n-1} \\sum_{j=i+1}^n \\frac{2}{j-i+1} \\\\\n",
    "&=& \\displaystyle \\sum_{i=1}^{n-1} \\sum_{k=1}^{n-i} \\frac{2}{k+1} \\\\\n",
    "&>& \\displaystyle \\sum_{i=1}^{n-1} \\sum_{k=1}^n \\frac{1}{k} \\\\\n",
    "&=& \\displaystyle \\sum_{i=1}^{n-1} \\Omega(\\lg n) \\\\\n",
    "&=& n\\Omega \\lg n\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.4-5\n",
    "\n",
    "> We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is \"nearly\" sorted. Upon calling quicksort on a subarray with fewer than $k$ elements, let it simply return without sorting the subarray. After the top-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process. Argue that this sorting algorithm runs in $O(nk + n \\lg(n/k))$ expected time. How should we pick $k$, both in theory and in practice?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "QUICK-SORT: layer number is $O(\\lg (n/k))$, therefore it is $O(n \\lg (n/k))$.\n",
    "\n",
    "INSERTION-SORT: each subarray is $O(k^2)$, the number of subarrays is $O(n/k)$, therefore it is $O(nk)$.\n",
    "\n",
    "Therefore this sorting algorithm runs in $O(nk + n \\lg(n/k))$.\n",
    "\n",
    "In practice we should use profiling."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.4-6 $\\star$\n",
    "\n",
    "> Consider modifying the PARTITION procedure by randomly picking three elements from array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst an $\\alpha$-to-$(1-\\alpha)$ split, as a function of $\\alpha$ in the range $0 < \\alpha < 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The worst case happens when at least two of the chose elements are in the $\\alpha n$ smallest or largest set, thus the probability of a worse case is \n",
    "\n",
    "$$\n",
    "2 \\left (\\alpha^3 + \\binom{3}{1}\\alpha^2(1-\\alpha)\\right )=6\\alpha^2-4\\alpha^3\n",
    "$$\n",
    "\n",
    "The complementary is $1-6\\alpha^2+4\\alpha^3$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
